package tree;
//输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/lhhy8s/
public class 判断是否为平衡二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //后序遍历 + 剪枝 （从底至顶）
    class Solution {
        public boolean isBalanced(TreeNode root) {
            if(root == null) return false;
            return recur(root) != -1;
        }
        private int recur(TreeNode root){
            if(root == null) return 0;
            int left = recur(root.left);
            if(left == -1) return -1;
            int right = recur(root.right);
            if(right == -1) return -1;
            return Math.abs(left - right) < 2 ? Math.max(left, right)+1 : -1;
        }
    }
    //先序遍历 + 判断深度 （从顶至底）
    class Solution2 {
        public boolean isBalanced(TreeNode root) {
            if(root == null) return true;
            return Math.abs(dfs(root.left) - dfs(root.right)) <= 1
                    && isBalanced(root.left) && isBalanced(root.right);
        }
        private int dfs(TreeNode root){
            if(root == null) return 0;
            return Math.max(dfs(root.left), dfs(root.right))+1;
        }
    }
}
